#lista = [2,40,1,30,5] #en c se usa un vector n+1 dimension

def insertion_sort(list2):
    for i in range(1, len(list2)):
        j = i
        while j > 0 and list2[j] < list2[j-1]:
            list2[j], list2[j - 1]  = list2[j-1], list2[j]  #swap
            j -= 1
    return list2

def posMenor(ls,i,n):
  posm = i
  for j in xrange(i+1,n):
    if ls[j] < ls [posm]:
      posm = j
  return posm    

def seleccion(ls):
  #en c, pasar n por parametro
  n=len(ls)
  for i in xrange(0,n):
    posm = posMenor(ls,i,n)
    #swap(ls[i],ls[posm])
    ls[i], ls[posm] = ls[posm], ls[i]
  return ls  

def burbuja(ls):
  #en c, pasar n por parametro
  n=len(ls)
  for i in xrange(0,n-1):
    for j in xrange(i+1,n):
      if ls[i] > ls[j]:
        ls[i], ls[j] = ls[j], ls[i]
  return ls      

def shell_sort(lista):
  n=len(lista)
  k=n/2
  while k>0:
    i=0
    while i+k<n:
      if lista[i]>lista[i+k]:
        lista[i], lista[i+k] = lista[i+k], lista[i] #swap
      i += 1
    k /= 2
  return lista 

def quicksort(ls):
  size = len(ls)
  pivot = ls[size/2]
  i=0
  j=size-1
  while i<j:
    while ls[i] < pivot:
      i += 1
    while ls[j] > pivot:
      j -= 1
    ls[i], ls[j] = ls[j], ls[i] #swap
  return ls

# mergesort
def mergeSort(toSort):
  if len(toSort) <= 1:
    return toSort
  mIndex = len(toSort) / 2
  left = mergeSort(toSort[:mIndex])
  right = mergeSort(toSort[mIndex:])
  result = []

  while len(left) > 0 and len(right) > 0:
    if left[0] > right[0]:  
      result.append(right.pop(0))
    else:
      result.append(left.pop(0))
  if len(left) > 0:
    result.extend(mergeSort(left))
  else:
    result.extend(mergeSort(right))
  return result
#mergesort end    

#MAIN
ls = [2,40,1,30,5]
lsi = [2,40,1,30,5,0,15]
#ls = [40,5]
#ls = [5]
print 'seleccion:', seleccion(ls)
print 'burbuja:', burbuja(ls)
print 'lsi:', lsi
print 'insertion_sort:', insertion_sort(lsi)
print 'shell_sort:', shell_sort(lsi)
print 'quicksort: ', quicksort(ls)
print 'mergesort:', mergeSort(lsi)
